from LeetCoder import *


class Solution:
    def rampartDefensiveLine(self, rampart: List[List[int]]) -> int:
        rampart.sort(key=lambda a: a[0])
        l, r = 0, rampart[-1][1]

        def f(m):
            l = rampart[0][1]
            for i in range(1, len(rampart) - 1):
                cur = rampart[i]
                L, R = cur[0] - l, rampart[i + 1][0] - cur[1]
                if L + R < m:
                    return False
                if L >= m:
                    l = cur[1]
                else:
                    l = m - L + cur[1]
            return True
        ans = 0
        while l <= r:
            m = ((r - l) >> 1) + l
            b = f(m)
            if b:
                ans = m
                l = m + 1
            else:
                r = m - 1
        return ans



s = Solution()
print(s.rampartDefensiveLine([[0, 3], [4, 5], [7, 9]]) == 3)
print(s.rampartDefensiveLine([[1, 2], [5, 8], [11, 15], [18, 25]]) == 4)
